package com.mlh.dp.old;
/*
    题目：
    假设有排成一行的N个位置，记为1~N，N-定大于或等于2。开始时机器人在其中的M位
    置上(M一定是1~N中的一个)，机器人可以往左走或者往右走，如果机器人来到1位置，那
    么下一步只能往右来到2位置;如果机器人来到N位置，那么下一步只能往左来到N-1位置。
    规定机器人必须走K步，最终能来到P位置(P也一-定是1~N中的一个)的方法有多少种。给
    定四个参数N、M、K、P，返回方法数。

    举例：
    N=5,M=2, K=3, P=3
    上面的参数代表所有位置为12345。机器人最开始在2位置上，必须经过3步，最后到
    达3位置。走的方法只有如下3种: 1)从2到1，从1到2，从2到3 2)从2到3，从3到2，从2到3
    3)从2到3，从3到4，从4到3
    所以返回方法数3。N=3, M=1, K=3, P=3
    .上面的参数代表所有位置为123。机器人最开始在1位置上，必须经过3步，最后到达3
    位置。怎么走也不可能，所以返回方法数0。

*/
public class RobotWalk {
    public static void main(String[] args) {
        System.out.println(method3(7, 4, 9, 5));
    }

    public static int method1(int allSite,int intiSite,int stepNum,int aimSite) {
        // 参数无效直接返回0
        if (allSite < 2 || stepNum < 1 || intiSite < 1 || intiSite > allSite || aimSite < 1 || aimSite > allSite) {
            return 0;
        }
        // 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
        return process(allSite,intiSite,stepNum,aimSite);
    }


    //第一步先实现暴力递归
    public static int process(int allSite,int intiSite,int stepNum,int aimSite){
        //0步的话  在aimSite则返回1否则返回0
        if(stepNum==0){
            return intiSite==aimSite?1:0;
        }
        //在1位置 只能向2位置走
        if(intiSite==1){
            return process(allSite,2,stepNum-1,aimSite);
        }
        //在allSite位置 只能向allSite-1位置走
        if(intiSite==allSite){
            return process(allSite,allSite-1,stepNum-1,aimSite);
        }
        //其他情况则是向左右走的方法数之和
        return process(allSite,intiSite-1,stepNum-1,aimSite)+process(allSite,intiSite+1,stepNum-1,aimSite);
    }
    //现在我们需要将暴力递归优化成记忆搜索，实际上记忆搜索就是记住了曾经已经算出结果的某种状态，下次再遇到这种状态就不需要再次进行计算了，以此达到降低复杂度的目的
    //在上面 我们可以看到allSite 和 aimSite实际上是固定的，而 intiSite 和 stepNum是变化的，如果intiSite 和 stepNum确定就可以计算出一个固定的结果
    //因此intiSite 和 stepNum的变化范围可以组成一个二维数组，二维数组每一个元素实际上就是对应确定的 intiSite 和 stepNum
    //填满这个二维数组一切的答案都出来了
    //本质也是递归，但是利用数组来记忆，相对于之前的暴力递归优化了
    public static int method2(int allSite,int intiSite,int stepNum,int aimSite){
        int[][] res=new int[allSite+1][stepNum+1];
        for(int i=0;i<res.length;i++){
            for(int j=0;j<res[0].length;j++){
                res[i][j]=-1;
            }
        }
        if (allSite < 2 || stepNum < 1 || intiSite < 1 || intiSite > allSite || aimSite < 1 || aimSite > allSite) {
            return 0;
        }
        return  process(allSite,intiSite,stepNum,aimSite,res);
    }

    public static int process(int allSite,int intiSite,int stepNum,int aimSite,int[][]res){
        if(res[intiSite][stepNum]!=-1){
            return res[intiSite][stepNum];
        }
        //0步的话  在aimSite则返回1否则返回0
        if(stepNum==0){
            res[intiSite][stepNum]=intiSite==aimSite?1:0;
            return res[intiSite][stepNum];
        }
        //在1位置 只能向2位置走
        if(intiSite==1){
            res[intiSite][stepNum]=process(allSite,2,stepNum-1,aimSite);
            return res[intiSite][stepNum];
        }
        //在allSite位置 只能向allSite-1位置走
        if(intiSite==allSite){
            res[intiSite][stepNum]=process(allSite,allSite-1,stepNum-1,aimSite);
            return  res[intiSite][stepNum];
        }
        //其他情况则是向左右走的方法数之和
        res[intiSite][stepNum]=process(allSite,intiSite-1,stepNum-1,aimSite)+process(allSite,intiSite+1,stepNum-1,aimSite);
        return res[intiSite][stepNum];
    }

    //在method2中  我们将首次计算出的结果记录在二维表中 达成了记忆搜索
    //接下来我们需要寻找二维表中的依赖关系，不再通过递归去完成表的填写，而是通过表依赖去完成
    //这个过程最好可以画图来推理，画图会比较清晰
    public static int method3(int allSite,int intiSite,int stepNum,int aimSite){
        int[][] res=new int[allSite+1][stepNum+1];
        //根据递归过程的base case, 把这张表的最简单、不需要依赖其他位置的那些位置填好值
        //然后根据之前写好的递归过程对表中内容进行填写，知道表依赖，这一步带具体数值会发现的快一点
        //发现表依赖后，就不用不管题目是什么了，直接按照表依赖把数组填完，所以答案也就出来了
        //没必要对表依赖强行做出解释，我们是从暴力递归一步一步走下来的，暴力递归就是我们最主要的一个想法，后面都是套路
        res[aimSite][0]=1;
        for(int j=1;j<res[0].length;j++){
            for(int i=1;i<res.length;i++){
                if(i==1){
                    res[i][j]=res[i+1][j-1];
                }else if(i==allSite){
                    res[i][j]=res[i-1][j-1];
                }else{
                    res[i][j]=res[i-1][j-1]+res[i+1][j-1];
                }
            }
        }
        return res[intiSite][stepNum];
    }
}
